package t945

import (
	"fmt"
	"sort"
)

func minIncrementForUnique(A []int) int {
	//输入：[1,2,2]
	//输出：1
	//解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

	//输入：[3,2,1,2,1,7]
	//输出：6
	//解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
	if len(A) == 0 {
		return 0
	}

	sort.Ints(A)

	cnt := make(map[int]int)
	extra := make([]int, 0)
	scope := make([]int, 0)

	last := A[0]

	for _, v := range A {
		sub := v - last
		if sub > 1 {
			for i := last + 1; i < v; i++ {
				if len(scope) < len(A) {
					scope = append(scope, i)
				}
			}
		}
		if _, ok := cnt[v]; ok {
			//拿到重复的数字,推到数组
			extra = append(extra, v)
		}
		cnt[v]++
		last = v
	}

	if len(scope) > 0 && scope[len(scope)-1] > last {
		last = scope[len(scope)-1]
	}

	last++
	sum := 0

	for _, v := range extra {
		el, err := Pop(&scope, v)
		if err == nil {
			sum += el - v
		} else {
			sum += last - v
			last++
		}
	}

	return sum
}

func Pop(a *[]int, v int) (int, error) {

	var err error

	if len(*a) == 0 {
		return 0, fmt.Errorf("array is empty")
	}

	el := (*a)[0]
	*a = (*a)[1:]

	if v > el {
		el, err = Pop(a, v)
		if err != nil {
			return 0, fmt.Errorf("array is empty")
		}
	}

	return el, nil
}
